/*
 * FlowGraph.java
 *
 * Created on August 31, 2006, 1:16 PM
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */

package com.smallx.xproc.compiler;

import com.smallx.xproc.ComputedPort;
import com.smallx.xproc.ForEach;
import com.smallx.xproc.Group;
import com.smallx.xproc.InlineDocument;
import com.smallx.xproc.PipelineModel;
import com.smallx.xproc.PipelineModelBuilder;
import com.smallx.xproc.PortReference;
import com.smallx.xproc.Reference;
import com.smallx.xproc.StaticReference;
import com.smallx.xproc.Step;
import com.smallx.xproc.StepContainer;
import com.smallx.xproc.Viewport;
import com.smallx.xproc.compiler.graph.Edge;
import com.smallx.xproc.compiler.graph.Lattice;
import com.smallx.xproc.compiler.graph.Vertex;
import com.smallx.xproc.library.LibraryComponents;
import java.net.URI;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.logging.Level;
import java.util.logging.Logger;
import org.infoset.xml.Name;

/**
 *
 * @author alex
 */
public class FlowGraph implements LibraryComponents {
   
   static Name NON_MATCHES = Name.create("non-matches");
   static Logger LOG = Logger.getLogger(FlowGraph.class.getName());
   PipelineModel pipeline;
   Lattice lattice;
   
   /** Creates a new instance of FlowGraph */
   public FlowGraph(PipelineModel owner) 
   {
      this.pipeline = owner;
   }
   
   protected String getPortId(Name stepName,Name portName) {
      return stepName.toString()+'#'+portName.toString();
   }
   
   protected Vertex getVertexForReference(PortReference pref) {
      StepContainer group = pipeline.getPipelineGroup();
      Step step = group.getStep(pref.getStepName());
      if (step instanceof StepContainer) {
         return lattice.getVertex(getPortId(pref.getStepName(),pref.getPortName()));
      } else {
         return lattice.getVertex(step.getName().toString());
      }
   }
   
   protected String getDirectedLabel(Name from,Name to) {
      if (from==null) {
         return "* \u2192 "+to;
      } else if (to==null) {
         return from+" \u2192 *";
      } else {
         return from+" \u2192 "+to;
      }
   }
   
   public void compile() 
   {
      lattice = new Lattice(pipeline.getName().toString());
      StepContainer group = pipeline.getPipelineGroup();
      for (Name portName : group.getComponentType().getInputPortNames()) {
         Vertex v = new Vertex(getPortId(group.getName(),portName));
         v.setName(portName);
         v.setType(IN_TYPE);
         lattice.addStart(v);
      }
      for (Name portName : group.getComponentType().getOutputPortNames()) {
         Vertex v = new Vertex(getPortId(group.getName(),portName));
         v.setName(portName);
         v.setType(OUT_TYPE);
         lattice.addEnd(v);
      }
      int sourceCount = 0;
      int generated = 0;
      // Add all regular steps and container representations as vertices
      for (Name name : group.getStepNames()) {
         Step step = group.getStep(name);
         if (step==group) {
            continue;
         }
         if (step instanceof Group || step instanceof ForEach) {
            boolean isGroup = step instanceof Group;
            String prefix = isGroup ? "group" : "for-each";
            for (Name portName : step.getComponentType().getInputPortNames()) {
               Vertex v = new Vertex(getPortId(name,portName));
               v.setName(Name.create(NAMESPACE,prefix+"-in-"+generated+"-"+name.getLocalName()));
               v.setType(isGroup ? GROUP_IN_TYPE : FOREACH_IN_TYPE);
               lattice.addVertex(v);
            }
            for (Name portName : step.getComponentType().getOutputPortNames()) {
               Vertex v = new Vertex(getPortId(name,portName));
               v.setName(Name.create(NAMESPACE,prefix+"-out-"+generated+"-"+name.getLocalName()));
               v.setType(isGroup ? GROUP_IN_TYPE : FOREACH_IN_TYPE);
               lattice.addVertex(v);
            }
         } else if (step instanceof Viewport) {
            Viewport viewport = (Viewport)step;
            Name inputPortName = step.getComponentType().getInputPortNames().iterator().next();
            Name outputPortName = step.getComponentType().getOutputPortNames().iterator().next();
            Vertex inputV = new Vertex(getPortId(name,inputPortName));
            PortReference inputRef = (PortReference)step.getInputBinding(inputPortName);
            inputV.setExpression(viewport.getExpression().getXPath(),viewport.getExpression().getNamespaceScope());
            /*
            if (inputRef instanceof ComputedPort) {
               ComputedPort cport = (ComputedPort)inputRef;
               inputV.setExpression(cport.getExpression().getXPath(),cport.getExpression().getNamespaceScope());
            } else {
               inputV.setExpression("/",step.getNamespaceScope());
            }*/
            generated++;
            inputV.setName(Name.create(NAMESPACE,"viewport-in-"+generated+"-"+name.getLocalName()));
            inputV.setType(VIEWPORT_START_TYPE);
            lattice.addVertex(inputV);
            Vertex outputV = new Vertex(getPortId(name,outputPortName));
            generated++;
            outputV.setName(Name.create(NAMESPACE,"viewport-out-"+generated+"-"+name.getLocalName()));
            outputV.setType(VIEWPORT_END_TYPE);
            lattice.addVertex(outputV);
            lattice.add(new Edge(inputV,NON_MATCHES,outputV,NON_MATCHES,true));
         } else {
            Name componentName = step.getComponentType().getName();
            String kind = componentName.getNamespaceName().equals(PipelineModelBuilder.NAMESPACE) ?
               componentName.getLocalName() :
               componentName.toString();
            Vertex v = new Vertex(name.toString(),name+" ("+kind+")");
            v.setName(name);
            v.setType(step.getComponentType().getName());
            lattice.addVertex(v);
            Map<Name,String> parameters = step.getParameters();
            if (parameters.size()>0) {
               v.getParameters().putAll(parameters);
            }
            v.setNamespaceScope(step.getNamespaceScope());
         }
      }
      
      // Add edges for input/output bindings
      for (Name name : group.getStepNames()) {
         Step step = group.getStep(name);
         // Step containers are different as their ports are vertices
         if (step instanceof StepContainer) {
            StepContainer container = (StepContainer)step;
            // Handle input uses inside the container
            for (Name portName : container.getComponentType().getInputPortNames()) {
               Vertex source = lattice.getVertex(getPortId(step.getName(),portName));
               if (source==null) {
                  throw new IllegalStateException("Cannot find vertex for "+getPortId(step.getName(),portName));
               }
               //Reference outsideRef = container.getInputBinding(portName);
               for (PortReference pref : container.getInputReferences(portName)) {
                  Vertex target = getVertexForReference(pref);
                  Edge e = new Edge(
                     source,
                     portName,
                     target,
                     pref.getPortName(),
                     true
                  );
                  
                  if (!target.getType().equals(VIEWPORT_START_TYPE)) {
                     Step stepTarget = group.getStep(pref.getStepName());
                     Reference ref = stepTarget.getInputBinding(pref.getPortName());
                     if (ref instanceof ComputedPort) {
                        ComputedPort cport = (ComputedPort)ref;
                        //System.out.println("Setting expression on edge from "+e.getSource().getLabel()+" to "+e.getTarget().getLabel()+" mapping "+e.getLabel()+" to "+cport.getExpression());
                        e.setExpression(cport.getExpression().getXPath(),cport.getExpression().getNamespaceScope());
                     }
                  }
                  lattice.add(e);
               }
            }
            // Handle output sources inside the container
            for (Name portName : container.getComponentType().getOutputPortNames()) {
               PortReference pref = container.getOutputSource(portName);
               lattice.add(new Edge(
                  getVertexForReference(pref),
                  pref.getPortName(),
                  lattice.getVertex(getPortId(step.getName(),portName)),
                  portName,
                  true
               ));
            }
            for (Name portName : step.getOutputBindings()) {
               Vertex source = lattice.getVertex(getPortId(step.getName(),portName));
               for (PortReference pref : step.getOutputBinding(portName)) {
                  Vertex targetV = getVertexForReference(pref);
                  Edge e = new Edge(source,portName,targetV,pref.getPortName(),true);
                  // See if the input is a computed port by following the reverse mapping
                  // as long as it is not a viewport input
                  if (!targetV.getType().equals(VIEWPORT_START_TYPE)) {
                     Step target = group.getStep(pref.getStepName());
                     Reference ref = target.getInputBinding(pref.getPortName());
                     if (ref instanceof ComputedPort) {
                        ComputedPort cport = (ComputedPort)ref;
                        //System.out.println("Setting expression on edge from "+e.getSource().getLabel()+" to "+e.getTarget().getLabel()+" mapping "+e.getLabel()+" to "+cport.getExpression());
                        e.setExpression(cport.getExpression().getXPath(),cport.getExpression().getNamespaceScope());
                     }
                  }
                  lattice.add(e);
               }
            }
         } else {
            Vertex source = lattice.getVertex(name.toString());
            for (Name portName : step.getOutputBindings()) {
               for (PortReference pref : step.getOutputBinding(portName)) {
                  Vertex targetV = getVertexForReference(pref);
                  Edge e = new Edge(source,portName,targetV,pref.getPortName(),true);
                  // See if the input is a computed port by following the reverse mapping
                  // as long as it is not a viewport input
                  if (!targetV.getType().equals(VIEWPORT_START_TYPE)) {
                     Step target = group.getStep(pref.getStepName());
                     Reference ref = target.getInputBinding(pref.getPortName());
                     if (ref instanceof ComputedPort) {
                        ComputedPort cport = (ComputedPort)ref;
                        //System.out.println("Setting expression on edge "+e.getLabel()+" to "+cport.getExpression());
                        e.setExpression(cport.getExpression().getXPath(),cport.getExpression().getNamespaceScope());
                     }
                  }
                  lattice.add(e);
               }
            }
            // Add in static mappings
            for (Name portName : step.getInputBindings()) {
               Reference ref = step.getInputBinding(portName);
               Vertex docSource = null;
               if (ref instanceof InlineDocument) {
                  sourceCount++;
                  docSource = new DocumentSourceVertex(SOURCE_TYPE.toString()+"_"+sourceCount,"document",((InlineDocument)ref).getDocument());
               } else if (ref instanceof StaticReference) {
                  sourceCount++;
                  URI location = ((StaticReference)ref).getLocation();
                  docSource = new LocationVertex(SOURCE_TYPE.toString()+"_"+sourceCount,location.toString(),location);
               }
               if (docSource!=null) {
                  docSource.setType(SOURCE_TYPE);
                  lattice.addVertex(docSource);
                  lattice.add(new Edge(docSource,SOURCE_PORT,source,portName,true));
               }
            }
         }
      }
   }
   
   public void analyze() {
      boolean finerLog = LOG.isLoggable(Level.FINER);
      
      Name notifyPortName = Name.create("notify");
      Name inputPortName = Name.create("input");
      Name outputPortName = Name.create("output");
      Name startPortName = Name.create("start");
      Name iterationName = Name.create("iteration");
      
      // remove joins
      int joinNumber = 0;
      List<Vertex> newVertices = new ArrayList<Vertex>();
      for (Vertex v : lattice.getVertices()) {
         Map<Name,Boolean> processed = new HashMap<Name,Boolean>();
         List<Set<Edge>> joins = new ArrayList<Set<Edge>>();
         for (Edge e : v) {
            if (processed.get(e.getOutputPort())!=null) {
               continue;
            }
            processed.put(e.getOutputPort(),Boolean.TRUE);
            Set<Edge> join = new HashSet<Edge>();
            for (Edge other : v) {
               if (other==e) {
                  continue;
               }
               if (other.getOutputPort().equals(e.getOutputPort())) {
                  join.add(e);
                  join.add(other);
               }
            }
            if (join.size()!=0) {
               if (finerLog) {
                  LOG.finer("Join on "+v.getLabel()+" for "+join.iterator().next().getOutputPort());
               }
               joins.add(join);
            }
         }
         for (Set<Edge> join : joins) {
            joinNumber++;
            Name from = join.iterator().next().getOutputPort();
            
            // Create the join vertex
            Name name = Name.create(NAMESPACE,"join-"+joinNumber);
            Vertex joinVertex = new Vertex(name.toString(),"join");
            joinVertex.setName(name);
            joinVertex.setType(JOIN_TYPE);
            newVertices.add(joinVertex);
            lattice.add(new Edge(v,from,joinVertex,inputPortName,true));
            
            // Remove and recreate the edges on the joinVertex
            int count = 0;
            for (Edge e : join) {
               count++;
               v.remove(e);
               lattice.remove(e);
               Edge newEdge = new Edge(joinVertex,Name.create("output"+count),e.getTarget(),e.getInputPort(),true);
               if (e.getExpression()!=null) {
                  newEdge.setExpression(e.getExpression(),e.getNamespaceScope());
               }
               lattice.add(newEdge);
            }
         }
      }
      for (Vertex v : newVertices) {
         lattice.addVertex(v);
      }
      newVertices.clear();
      
      lattice.index();
      
      int inputGateNumber = 0;
      // remove flows that are into iteration subgraphs
      for (Vertex v : lattice.getVertices()) {
         if (v.getType()==null) {
            throw new IllegalStateException("Vertex "+v.getLabel()+" does not have a type.");
         }
         if (v.getType().equals(VIEWPORT_START_TYPE)) {
            Set<Vertex> subgraph = viewportSubgraph(v);
            Name sourceName = iterationName;
            /*
            LOG.info("Viewport subgraph for "+v.getLabel());
            for (Vertex member : subgraph) {
               LOG.info(member.getLabel());
            }*/
            for (Vertex member : subgraph) {
               if (member==v) {
                  continue;
               }
               Set<Edge> inbound = lattice.getInbound(member);
               if (inbound!=null) {
                  for (Edge outside : inbound) {
                     if (!subgraph.contains(outside.getSource()) && !outside.getSource().getType().equals(SOURCE_TYPE)) {
                        LOG.finer("Meet inside subgraph on "+member.getLabel()+" port "+outside.getInputPort()+" from outside source "+outside.getSource().getLabel()+" port "+outside.getOutputPort());
                        inputGateNumber++;

                        // Create the gate vertex for the input
                        Name name = Name.create(NAMESPACE,"gate-"+inputGateNumber);
                        Vertex gateVertex = new Vertex(name.toString(),"gate");
                        gateVertex.setName(name);
                        gateVertex.setType(GATE_TYPE);
                        newVertices.add(gateVertex);

                        // Remove the old edge
                        lattice.remove(outside);
                        outside.getSource().remove(outside);

                        // Add a notify edge to the new vertex from the viewport start
                        lattice.add(new Edge(v,sourceName,gateVertex,notifyPortName,true));

                        // Add an edge to the new vertex from the outside vertex
                        lattice.add(new Edge(outside.getSource(),outside.getOutputPort(),gateVertex,inputPortName,true));

                        // Add an edge from the new vertex from the inside vertex
                        lattice.add(new Edge(gateVertex,outputPortName,outside.getTarget(),outside.getInputPort(),true));

                     }
                  }
               }
            }
         }
      } 
      for (Vertex v : newVertices) {
         lattice.addVertex(v);
      }
      
      int computeNumber = 0;
      List<Edge> newEdges = new ArrayList<Edge>();
      List<Edge> removeEdges = new ArrayList<Edge>();
      // Remove computed edges
      for (Edge e : lattice) {
         if (e.getExpression()!=null) {
            computeNumber++;
            Name name = Name.create(NAMESPACE,"compute-"+computeNumber);
            Vertex compute = new Vertex(name.toString(),"compute");
            compute.setName(name);
            compute.setType(COMPUTE_TYPE);
            compute.setExpression(e.getExpression(),e.getNamespaceScope());
            lattice.addVertex(compute);
            
            Edge fromEdge  = new Edge(e.getSource(),e.getOutputPort(),compute,inputPortName,true);
            newEdges.add(fromEdge);
            Edge toEdge  = new Edge(compute,outputPortName,e.getTarget(),e.getInputPort(),true);
            newEdges.add(toEdge);
            
            removeEdges.add(e);
         }
      }
      for (Edge e : newEdges) {
         lattice.add(e);
      }
      for (Edge e : removeEdges) {
         lattice.remove(e);
         e.getSource().remove(e);
      }
      
   }
   
   public Set<Vertex> viewportSubgraph(Vertex start) {
      Vertex end = null;
      Edge toEnd = null;
      for (Edge e : start) {
         if (e.getTarget().getType().equals(VIEWPORT_END_TYPE)) {
            end = e.getTarget();
            toEnd = e;
            break;
         }
      }
      if (end==null) {
         throw new IllegalStateException("Cannot find end of viewport for "+start.getLabel());
      }
      Set<Vertex> subgraph = new HashSet<Vertex>();
      subgraph.add(start);
      subgraph.add(end);
      List<Edge> toCheck = new ArrayList<Edge>();
      List<Edge> added = new ArrayList<Edge>();
      for (Edge e : start) {
         Name type = e.getTarget().getType();
         if (!type.equals(FlowGraph.GATE_TYPE) &&
             !type.equals(FlowGraph.VIEWPORT_START_TYPE)) {
            toCheck.add(e);
         }
      }
      //toCheck.remove(toEnd);
      while (!toCheck.isEmpty()) {
         for (Edge e : toCheck) {
            subgraph.add(e.getTarget());
            if (e.getTarget()!=end) {
               // Exclude all container subgraphs but add their edge to the end end
               if (e.getTarget().getType().equals(VIEWPORT_START_TYPE)) {
                  for (Edge other : e.getTarget()) {
                     if (other.getTarget().getType().equals(VIEWPORT_END_TYPE)) {
                        added.add(other);
                     }
                  }
               } else {
                  // Otherwise add all the edges
                  added.addAll(e.getTarget());
               }
            }
         }
         List<Edge> saved = toCheck;
         toCheck = added;
         saved.clear();
         added = saved;
      }
      return subgraph;
   }
   
   public Lattice getLattice() {
      return lattice;
   }
   
   public PipelineModel getPipeline() {
      return pipeline;
   }
   /*
   
   protected List<Step> getLongestPath(StepContainer container) {

      List<Step> path = new ArrayList<Step>();
      List<Step> longest = null;
      Name longestStart = null;
      int depth = -1;
      List<Iterator<Name>> pathState = new ArrayList<Iterator<Name>>();
      for (Name containerInput : container.getComponentType().getInputPortNames()) {
         for (PortReference flowInputRef : container.getInputReferences(containerInput)) {
            Name stepName = flowInputRef.getStepName();
            // Ignore if the step is already assigned
            if (assignedSteps.get(stepName)!=null) {
               continue;
            }
            // Ignore if the step is a descendant but not a child
            Step firstStep = container.getStep(stepName);
            if (firstStep.getContainer()!=container) {
               continue;
            }
            // Follow the chain
            pathState.clear();
            Step current = firstStep;
            path.add(current);
            pathState.add(current.getComponentType().getOutputPortNames().iterator());
            depth++;
            while (current!=null) {
               Iterator<Name> outputs = pathState.get(depth);
               if (!outputs.hasNext()) {
                  path.remove(depth);
                  pathState.remove(depth);
                  depth--;
               }
               Name outputName = outputs.next();
               PortReference outputBinding = (PortReference)current.getOutputBinding(outputName);
               Step nextStep = container.getStep(outputBinding.getStepName());
            }
         }
      }
      return longest;
   }*/
   
}
